package scatter.interview.rest.interview.i1_queue;

/**
 * Created by yangwei
 * Created at 2020/12/2 17:19
 */
public class LinkQuene<T> extends AbstractQuene<LinkQuene.QNode, LinkQuene.QNode, T>{



    //初始化
    public LinkQuene(){
        this.front = new QNode<T>();
        this.rear = new QNode<T>();
        this.size = 0;
    }

    //初始化队列
    public void initQueue(){
        front.next = null;
        rear.next = null;
        size = 0;
    }

    //队空判断
    public boolean isNull(){
        return front.next==null || rear.next==null;
    }

    //进队
    @Override
    public boolean push(T t){
        QNode<T> node = new QNode<>(t);
        if(isNull()){
            //第一次
            front.next = node;
            rear.next = node;
            size++;
        }
        else{
            node.next = front.next;
            front.next = node;
            size++;
        }
        return true;
    }


    //出队
    @Override
    public T pop(){
        if(isNull()) {
            return null;//队为空时，无法出队
        }
        else if(size==1){
            //队只有一个元素时直接初始化即可
            QNode<T> node  = front.next;
            initQueue();
            return node.data;
        }
        else{
            //准备工作
            QNode<T> p = front;//使用p指针来遍历队列
            for(int i=1;i<size-1;i++){
                p = p.next;
            }

            //pop
            QNode<T> node = rear.next;
            rear.next = p.next;
            size--;
            return node.data;
        }
    }

    //链队结点
    class QNode<T>{
        private T data;//数据域
        public QNode<T> next;//指针域

        //初始化1
        public QNode(){
            this.data = null;
            this.next = null;
        }
        //初始化2
        public QNode(T data){
            this.data = data;
            this.next = null;
        }

        public T getData() {
            return data;
        }
        public void setData(T data) {
            this.data = data;
        }

    }


    public static void main(String[] args) {
        LinkQuene<String> sQueue = new LinkQuene<>();
        sQueue.push("1");
        sQueue.push("2");
        sQueue.push("3");
        sQueue.push("4");
        System.out.println(sQueue.pop());
        System.out.println(sQueue.pop());
        System.out.println(sQueue.pop());
        System.out.println(sQueue.pop());
        System.out.println(sQueue.pop());
    }
}
